package com.fps.webshop.question.question0001_0099;

import com.fps.webshop.question.common.ListNode;

/**
 * 83. 删除排序链表中的重复元素
 * 
 * 存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。
 * 
 * 返回同样按升序排列的结果链表。
 * 
 * 示例 1：
 * Question083_01.jpg
 * 输入：head = [1,1,2]
 * 输出：[1,2]
 * 
 * 示例 2：
 * Question083_02.jpg
 * 输入：head = [1,1,2,3,3]
 * 输出：[1,2,3]
 * 
 * 提示：
 * 		链表中节点数目在范围 [0, 300] 内
 * 		-100 <= Node.val <= 100
 * 		题目数据保证链表已经按升序排列
 */
public class Question083 {
	
	/**
	 * 第一次提交，链表遍历循环，还行
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		0 ms	37.9 MB	Java	2021/08/17 16:17
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：37.9 MB, 在所有 Java 提交中击败了55.71%的用户
	 */
	public static ListNode deleteDuplicates(ListNode head) {
		ListNode startNode = head;
		while(head!=null) {
			if(head.next!=null&&head.val == head.next.val) {
				head.next = head.next.next;
			}else {
				head = head.next;
			}
		}
		return startNode;
    }
	
	/**
	 * 第二次提交，尝试使用递归
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		0 ms	38 MB	Java	2021/08/17 16:20
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：38 MB, 在所有 Java 提交中击败了40.34%的用户
	 */
	public ListNode deleteDuplicates2(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return head;
        }
        if (head.val == head.next.val) {
            head = deleteDuplicates2(head.next);
        } else {
            head.next = deleteDuplicates2(head.next);
        }
        return head;
    }
	
	
	public static void main(String[] args) {
		ListNode l5 = new ListNode();
		l5.val = 5;
		l5.next=null;
		
		ListNode l4 = new ListNode();
		l4.val = 5;
		l4.next=l5;
		
		ListNode l3 = new ListNode();
		l3.val = 3;
		l3.next=l4;
		
		ListNode l2 = new ListNode();
		l2.val = 3;
		l2.next=l3;
		
		ListNode l1 = new ListNode();
		l1.val = 1;
		l1.next=l2;
		
		ListNode l = deleteDuplicates(l1);
		while(l!=null) {
			System.out.print(l.val+" ");
			l = l.next;
		}
	}
}
